Typical computer file systems store file data in small, fixed-size blocks, referred to by pointers maintained in metadata associated with each file. In the event two pointers refer to identical blocks, some storage capacity can be reclaimed by changing one or both pointers so that they refer to the same block. The process of finding pointers that refer to identical blocks and then changing one or both pointers so that they point to the same block is referred to herein as “deduplication”. Such deduplication is typically performed by a gateway that controls access by host computers to the storage medium.